package javaJob.exercise.primary.other;

import java.util.ArrayList;
import java.util.List;

public class primary46_answer {

    public List<List<Integer>> generate(int numRows) {
        /*List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i=0; i<numRows; i++) {
            List<Integer> subList = new ArrayList<Integer>();
            for (int j=0; j<=i; j++) {
                if (j==0 || j==i) {
                    //一行的头和尾都是1
                    subList.add(1);
                } else {
                    //上一行
                    List<Integer> up = list.get(i-1);
                    //上一行左侧的值 + 上一行右侧的值
                    subList.add(up.get(j-1) + up.get(j));
                }
            }
            list.add(subList);
        }
        return list;*/
        List<List<Integer>> list=new ArrayList<>();
        int[] a=new int[numRows];
        for(int i=0;i<numRows;i++){
            merge(a,i);
            List<Integer> list2=new ArrayList<>();
            for(int j=0;j<=i;j++){
                list2.add(a[j]);
            }
            list.add(list2);
        }
        return list;
    }
    public void merge(int[] a,int i){
        if(a[i]>0){
            return;
        }
        if(i==0){
            a[0]=1;
            return;
        }
        merge(a,i-1);
        for(int j=i;j>0;j--){
            a[j]=a[j]+a[j-1];
        }
    }

}
